Rustication
Authentication is a process by which a prover assures a verifier that the prover has a claimed identity. A thorough description is provided by Menezes et al., “Handbook of applied cryptography,” CRC Press, 1997, and Schneier “Applied cryptography,” Wiley, 1996.
Two primary objectives of the authentication protocol are completeness and soundness. Completeness means that the prover can always complete the authentication. Soundness means that an imposter has a negligible probability of completing the authentication.
There are various grades of dishonesty and corresponding levels of security. In a conventional security framework, it is assumed that the imposter can make multiple attacks on the prover, Feige et al., “Zero knowledge proofs of identity,” Journal of Cryptology, Vol. 1, pp. 77-94, 1988.
A typical requirement of the authentication protocol is that the protocol is secure against impersonation under passive attack, where an adversarial prover has access to transcripts of prover-verifier interactions. A stronger requirement is that the protocol is secure against active attacks. Here, an adversarial prover can actively play the role of a cheating verifier with the prover numerous times before the impersonation attempt.
It is also desired to secure against concurrent attacks. In these attacks, an adversarial prover plays the role of a cheating verifier prior to impersonation. A key distinction is that the imposter interacts concurrently with multiple honest provers.
It is also desired that the authentication process does not reveal any secret information, e.g., the identity of the prover. This is known as zero knowledge authentication. A lucid and non-mathematical presentation of the concept of zero knowledge is provided by Quisquater et al., “How to explain zero knowledge protocols to your children,” Advances in Cryptology—CRYPTO '89, LNCS 435, pp. 628-631, 1989.
With the zero knowledge authentication protocol, the prover convinces the verifier that the prover is in possession of knowledge of a secret, without revealing the secret itself. This is unlike a conventional password protocol, where the prover must reveal the secret to the verifier in order to authenticate.
It is very important to keep in mind that the authentication protocol provides assurances only at the instant in time when the protocol is successfully completed. It is therefore important to ensure that the authentication process is tied to some form of ongoing security service. At some level, all authentication protocols are vulnerable to the adversary who cuts in immediately after the successful authentication of the prover.
Zero knowledge protocols allow the prover to demonstrate knowledge of the secret while revealing no information whatsoever other than the fact the prover possesses the secret, Goldwasser et al., “The knowledge complexity of interactive proof-systems,” Proceedings of the 17th Annual ACM Symposium on Theory of Computing, pp. 291-304, 1985, and U.S. Pat. No. 4,995,082, “Method for identifying subscribers and for generating and verifying electronic signatures in a data exchange system,” issued to Schnorr on Feb. 19, 1991.
An interactive protocol is said to be a proof of knowledge when there exists an algorithm that can always extract the secret. A protocol is said to be zero knowledge when it does not reveal the secret. As an advantage, the zero knowledge protocol does not suffer a degradation from repeated use and resists all attempts at impersonation.
A protocol is said to be honest-verifier zero knowledge if it is zero knowledge when interacting with honest verifiers. The honest-verifier zero knowledge protocol has a weaker security guarantee than the general zero knowledge protocol because it is possible that a dishonest verifier can extract the secret.
The ultimate measure of the worth of the authentication protocol lies in its security against impersonation attempts. A protocol that is secure against impersonation under concurrent attacks is considered to be “secure” even if it is only honest-verifier zero knowledge.
For a detailed and exhaustive discussions on authentication protocols including biometric techniques, see Davies et al., “Security for computer networks,” Wiley, 1989, and Ford, “Computer communications security: principles, standard protocols and techniques,” Prentice Hall, 1994. Password based schemes including the concept of salting are described by Morris et al., “Password security: a case history,” Communications of the ACM, Vol. 22, pp. 594-597, 1979, also see Needham et al., “Using encryption for authentication in large networks of computers,” Communications of the ACM, Vol. 21, pp. 993-999, 1978.
Feige et al. adapted the concepts of zero knowledge to the application of authentication and proofs of knowledge. Since then there has been a veritable explosion of research into various aspects of zero knowledge, see Schneier “Applied cryptography,” Wiley, 1996.
Conventional zero knowledge protocols require the interchange of a substantially amount of data between the prover and the verifier. The processing of the protocol also takes substantial computer resources. Therefore, zero proof knowledge protocols have only been feasible on high-complexity systems with a substantial communications bandwidth and memory, and a relatively sophisticated microprocessor. Such systems are relatively expensive and complex to build, operate and maintain.
However, there are an increasing number of low-complexity, hand-held devices with severely limited resources. Many of these device use microcontrollers instead of microprocessors. For a microprocessor to be useful it must be attached to RAM, disks, keyboards, and other I/O peripherals. Operating systems and applications programs need to be installed. A microprocessor chip, by itself has no use.
Not so for a microcontroller, which can be used as is. It usually has on-chip memory and for mass-produced controller, software is factory installed. As an advantage, microcontrollers are cheap to produce and simple to operate. There is no maintenance, because their low price makes them essentially disposable.
Therefore, it is desired to provide a simple, low-bandwidth zero knowledge protocol, which can operate with microcontrollers.